package leetcode.editor.cn;

import java.util.HashMap;

public class P424LongestRepeatingCharacterReplacement {
    public static void main(String[] args) {
        Solution solution = new P424LongestRepeatingCharacterReplacement().new Solution();
        System.out.println(solution.characterReplacementMy("ABBB", 1));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int characterReplacement(String s, int k) {
            int len = s.length();
            if (len < 2) {
                return len;
            }

            char[] charArray = s.toCharArray();
            int left = 0;
            int right = 0;

            int res = 0;
            int maxCount = 0;
            int[] freq = new int[26];
            // [left, right) 内最多替换 k 个字符可以得到只有一种字符的子串
            while (right < len) {
                freq[charArray[right] - 'A']++;
                // 在这里维护 maxCount，因为每一次右边界读入一个字符，字符频数增加，才会使得 maxCount 增加
                maxCount = Math.max(maxCount, freq[charArray[right] - 'A']);
                right++;

                if (right - left > maxCount + k) {
                    // 说明此时 k 不够用
                    // 把其它不是最多出现的字符替换以后，都不能填满这个滑动的窗口，这个时候须要考虑左边界向右移动
                    // 移出滑动窗口的时候，频数数组须要相应地做减法
                    freq[charArray[left] - 'A']--;
                    left++;
                }
                res = Math.max(res, right - left);
            }
            return res;
        }

        public int characterReplacementMy(String s, int k) {
            char[] arr = s.toCharArray();
            int left = 0, right = 0;
            Integer max = 0;
            HashMap<Character, Integer> map = new HashMap<>();
            while (right < arr.length) {
                char c = arr[right];
                map.compute(c, (character, integer) -> {
                    if (integer == null) {
                        return 1;
                    }
                    return integer + 1;
                });
                Integer integer = map.get(c);
                max = Math.max(integer, max);
                right++;
                if (right - left > max + k) {
                    map.compute(c, (character, integer1) -> integer1 - 1);
                    left++;
                }
                max = Math.max(right-left, max);
            }
            return max;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)
}